МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА»
ДОСЛІДЖЕННЯ КОДОУТВОРЕННЯ ТА ПРИНЦИПІВ ПОБУДОВИ
КОДЕРІВ І ДЕКОДЕРІВ КОДІВ ХЕМІНГА
ІНСТРУКЦІЯ
до лабораторної роботи № 1
з курсу “ Основи збору, передачі та обробки інформації”
для студентів базового напряму 6.1601
“Захист інформації”
Затверджено
на засiданнi кафедри
"Захист інформації"
Протокол N вiд . .2007 p.
Львів 2007
Дослідження кодоутворення та принципів побудови кодерів і декодерів кодів Хемінга: Інструкція до лабораторної роботи № 1 з курсів «Основи збору, передачі та обробки інформації» для студентів базового напрямку «Захист інформації» усіх форм навчання / Укл. М. В. Кіріанакі, В. В. Хома, В. І. Отенко, Я. Р. Совин. – Львів: НУЛП, 2007. – 13 с.
Укладачі: М. В. Кіріанакі, канд. техн. наук, доц., В. В. Хома, док. техн. наук, проф., В. І. Отенко, канд. техн. наук, доц., Я. Р. Совин, асист.
Відповідальний за випуск М. В. Кіріанакі, канд. техн. наук, доц.
Рецензенти: З. Р. Мичуда, канд. техн. наук, доц., О. В. Івахів, канд. техн. наук, доц.
Складання і відлагодження схеми здійснено асист. каф. захисту інформації Совином Я. Р.
мета роботи – вивчити принципи побудови кодів Хемінга та одержати практичні навики розробки функціональних схем кодерів і декодерів.
ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Простота реалізації та ефективне забезпечення завадостійкості зумовили широке застосування коду Хемінга (КХ) не лише у телемеханіці, але і в обчислювальній техніці та зв’язку. Відомі декілька різновидностей КХ, які характеризуються різною коректуючою здатністю [1, 2]. Код Хемінга з d = 3 забезпечує виявлення двократних (r = 2) або виправлення однократної (S = 1) помилки, оскільки d = r + 1 або d = 2S + 1.
Вихідним для коду Хемінга є первинний (двійковий або двійково-десятковий) EMBED Equation.3 -розрядний код, до якого в результаті вторинного кодування додають EMBED Equation.3 контрольних розрядів. Отже, загальна довжина кодової комбінації (КК) збільшиться до EMBED Equation.3 .
Кількість робочих комбінацій EMBED Equation.3 . Число контрольних розрядів знаходять із виразу [2, 3]:
EMBED Equation.3 (1)
В табл. 1 наведені значення п і EMBED Equation.3 , для різних EMBED Equation.3 , що задовільняють умову (1).
Таблиця 1
Оскільки при збільшенні кількості інформаційних розрядів EMBED Equation.3 , кількість контрольних розрядів EMBED Equation.3 зростає незначно, надлишковість коду,
EMBED Equation.3 (2)
зменшується, а швидкість передачі інформації
EMBED Equation.3 (3)
зростає.
Побудова коду Хемінга, що виправляє всі одиничні помилки (d = 3) здійснюється так. Спочатку визначають необхідну кількість контрольних розрядів на підставі співвідношення (1). Далі визначають їх розташування в кодовій комбінації. Для спрощення кодування і декодування контрольні символи розташовують на місцях КК, кратних степеню 2, тобто на позиціях 1, 2, 4, 8, 16 і т.д., хоча їх розташування може бути довільним. Інформаційні розряди розташовуються на вільних місцях. На основі зазначеного для 15-розрядної кодової комбінації можна записати:
EMBED Equation.3
де І3 перший (молодший), а І15 одинадцятий (старший) розряд робочої (інформаційної) КК.
У циклічному коді Хемінга контрольні символи розташовуються після інформаційних розрядів [4].
Потім знаходять значення контрольних символів (0 або 1) підсумовуючи за модулем два (перевірка на парність) значення певних інформаційних розрядів за алгоритмом Хемінга так:
EMBED Equation.3 . (4)
EMBED Equation.3 ; (5)
...